import com.sun.xml.internal.ws.util.StringUtils;
import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;

public class Offer48 {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode tmpNode = q.poll();
            if(tmpNode == null){
                sb.append("$,");
            }
            else {
                sb.append(String.valueOf(tmpNode.val) + ',');
                q.add(tmpNode.left);
                q.add(tmpNode.right);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("")){
            return null;
        }
        String[] strNodeArr = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(strNodeArr[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int ind = 1;
        while(!q.isEmpty()){
            TreeNode tmpNode = q.poll();
            String leftStr = strNodeArr[ind++];
            String rightStr = strNodeArr[ind++];
            if(!leftStr.equals("$")){
                tmpNode.left = new TreeNode(Integer.valueOf(leftStr));
                q.add(tmpNode.left);
            }
            if(!rightStr.equals("$")){
                tmpNode.right = new TreeNode(Integer.valueOf(rightStr));
                q.add(tmpNode.right);
            }
        }
        return root;
    }
}
